package org.czl.gh;

public class floyd {
    public static void main(String[] args) {
        //[[0,1,3],[1,2,1],[1,3,4],[2,3,1]]
        findTheCity(4, new int[][]{{0,1,3},{1,2,1}, {1,3,4}, {2,3,1}}, 4);
    }
    public static int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] path = new int[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                path[i][j] = Integer.MAX_VALUE;
            }
        }
        for(int[] e : edges){
            path[e[0]][e[1]] = e[2];
            path[e[1]][e[0]] = e[2];
        }

        for(int f = 0; f < n; f++){
            for(int i = 0; i < n; i++){
                for(int j = 0; j < n; j++){
                    if(path[i][f] != Integer.MAX_VALUE && path[f][j] != Integer.MAX_VALUE &&
                            path[i][j] > path[i][f] + path[f][j]){
                        path[i][j] = path[i][f] + path[f][j];
                    }
                }
            }
        }
        int ans = n - 1;
        int num = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            int count = 0;
            for(int j = 0; j < n; j++){
                if(j != i && path[i][j] <= distanceThreshold){
                    count++;
                }
            }
            if(count <= num){
                num = count;
                ans = i;
            }
        }
        return ans;
    }
}
